import pprint as pp
import itertools as it

def hamilton_path(matrix):
    poss = dict()
    n = len(matrix)

    # get all subsets of length 1, 2, 3, 4, 5...
    for length in range(1, n + 1):
        for subset in it.combinations(range(n), length):
            poss[subset] = dict()

            num_vertices = len(subset)

            # if there is one node, then it is a hamilton path
            if num_vertices == 1:
                poss[subset][subset[0]] = True
                continue

            # there are at least 2 vertices in the set
            # For each choice of S and v, a path exists for (S,v) if and only if v has a
            #   neighbor w such that a path exists for (S − v,w), which can be looked up
            for vertex in subset:
                path_exists = False

                #get the neighbors
                neighbors = []
                for i in range(n):
                    if matrix[vertex][i]: neighbors.append(i)

                # create S-v
                new_subset = tuple(x for x in subset if x != vertex)
                for neighbor in neighbors:
                    if neighbor in poss[new_subset] and poss[new_subset][neighbor]:
                        path_exists = True
                        break

                poss[subset][vertex] = path_exists

    # pp.pprint(poss)

    # see if there is a hamilton path in the entire graph
    for x in poss[tuple(range(n))]:
        if x:
            return True

    return False
if __name__ == "__main__":
    matrix = [
            [0, 1, 0, 0, 1],
            [1, 0, 1, 1, 1],
            [0, 1, 0, 1, 0],
            [0, 1, 1, 0, 1],
            [1, 1, 0, 1, 0]
            ]
    print(hamilton_path(matrix))